Thực đơn
Sắp_xếp_chèn Thuật toánCơ sở lập luận của sắp xếp chèn có thể mô tả như sau:Xét danh sách con gồm k phần tử đầu a 1 , . . . , a k {\displaystyle a_{1},...,a_{k}} . Với k = 1, danh sách gồm một phần tử đã được sắp. Giả sử trong danh sách k-1 phần tử đầu a 1 , . . . , a k − 1 {\displaystyle a_{1},...,a_{k-1}} đã được sắp. Để sắp xếp phần tử a k = x {\displaystyle a_{k}=x} ta tìm vị trí thích hợp của nó trong dãy a 1 , . . . , a k − 1 {\displaystyle a_{1},...,a_{k-1}} . Vị trí thích hợp đó là đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.
Các phần tử ≤x | Vị trí thích hợp | Các phần tử>x | Các phần tử chưa sắp | ||||||
a 1 {\displaystyle a_{1}} | ... | a i − 1 {\displaystyle a_{i-1}} | x | a i + 1 {\displaystyle a_{i+1}} | ... | a k − 1 {\displaystyle a_{k-1}} | a k + 1 {\displaystyle a_{k+1}} | ... | a n {\displaystyle a_{n}} |
Thực đơn
Sắp_xếp_chèn Thuật toánLiên quan
Sắp xếp nổi bọt Sắp xếp trộn Sắp xếp chèn Sắp xếp vun đống Sắp xếp nhanh Sắp xếp tô pô Sắp xếp chọn Sắp xếp theo cơ số Sắp xếp Sắp xếp đếm phân phốiTài liệu tham khảo
WikiPedia: Sắp_xếp_chèn http://www.cs.ubc.ca/spider/harrison/Java/sorting-... http://coderaptors.com/?InsertionSort http://electrofriends.com/source-codes/software-pr... http://www.pathcom.com/~vadco/binary.html http://www.sorting-algorithms.com/insertion-sort http://citeseerx.ist.psu.edu/viewdoc/summary?doi=1... http://www.cs.sunysb.edu/~bender/newpub/BenderFaMo... http://www.algolist.net/Algorithms/Sorting/Inserti... http://dl.acm.org/citation.cfm?id=1132705 http://literateprograms.org/Category:Insertion_sor...